Relatório Final

Otimização de agendamento de filmes

Por João Zsigmond

Definição do Problema

A partir de uma lista de filmes categorizados, como podemos maximizar o número de filmes assistidos e o tempo assistindo filmes, respeitando os limites de cada categoria.

Input

Recebemos como entrada uma lista de filmes definidos por:

  1. horário de início
  2. horário de término
  3. categoria

E também recebemos o limite de filmes que podem ser assistidos por categoria.

A Heurística Gulosa

A heurística gulosa, em termos gerais, ordena os filmes por ordem crescente com relação ao horário de término e seleciona sempre o próximo filme na lista. Se o próximo filme na lista não pode ser assistido pois não se enquadra nas regras, ele é pulado. Um filme não se encaixa nas regras quando 1. já alcancamos o limite de filmes que podem ser assistidos em sua categoria ou 2. o filme tem início antes que o último filme chegou ao fim, dessa forma, se o assistirmos estaríamos assistindo dois filmes simultanteamente.

Código fonte da heurística gulosa

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

// Define a struct to represent a movie
struct Movie {
    int start_time;
    int end_time;
    int category;
};

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();

    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    // Read the category limits into a vector
    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    // Read the movie information into a vector
    vector<Movie> movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
        if (movies[i].end_time < movies[i].start_time) {
            movies[i].end_time = 24;
        }

        if (movies[i].end_time == movies[i].start_time) {
            movies[i].end_time += 1;
        }
    }

    // Sort the movies by end time
    sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
        if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
        return a.end_time < b.end_time;
    });

    // // Sort the movies by start time
    // sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
    //     return a.start_time < b.start_time;
    // });

    // Define a bitset to represent the availability of each hour of the day
    bitset<24> hours;

    // Keep track of how many movies of each category have been watched
    vector<int> num_watched(num_categories + 1, 0);

    // Keep track of the indices of the watched movies
    vector<int> watched;

    int time_watched = 0;

    // Iterate over the movies and check if each movie can be watched
    for (int i = 0; i < num_movies; i++) {
        const Movie& movie = movies[i];

        // Check if any hour of the movie overlaps with an already watched movie
        bool can_watch = true;
        for (int hour = movie.start_time; hour < movie.end_time; hour++) {
            if (hours[hour]) {
                can_watch = false;
                break;
            }
        }
        if (hours[movie.start_time]) { can_watch = false; }

        // If the movie can be watched and its category limit has not been reached,
        // mark the hours as watched, add the movie to the list of watched movies,
        // and print the start time, end time, and category of the movie
        if (can_watch && num_watched[movie.category] < category_limit[movie.category]) {
            num_watched[movie.category]++;
            time_watched += movie.end_time - movie.start_time;
            watched.push_back(i);
            hours[movie.start_time] = true;
            for (int hour = movie.start_time; hour < movie.end_time; hour++) {
                hours[hour] = true;
            }
            cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
        }
    }

    // Output the number of watched movies
    cout << "\nNúmero de filmes: " << watched.size() << endl;
    cout << "Tempo de tela (em horas): " << time_watched << endl;

    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação do código fonte da heurística gulosa

  1. Tratamento do input

Sempre começamos tratando os dados do input. Recebemos como entrada do nosso programa um arquivo na seguinte estrutura: primeira linha contem dois números, o número total de filmes e o número total de categorias. A segunda linha possui os limites de cada categoria. As linhas seguintes definem os filmes. Cada uma delas possuem 3 números, horário de início, horário de término e categoria. Começamos montando uma estrutura de dados para representar cada filme. Depois, transformamos os limites de cada categoria em um vetor e os filmes em um vetor de filmes.

  1. Ordenação

O segundo passo é ordenar o vetor de filmes por horário de término.

  1. Uso do bitset

Usamos um bitset para organizar quais horas do dia estão livres para assisitirmos um filme. Sempre que um novo filme é assistido, preenchemos o bitset nos horários que o filme nos ocupou.

  1. Validação do filme seguinte

Fazemos um loop no vetor de filmes e vamos assistindo um em seguida do outro. Sempre, antes de assistir um filme temos que verificar se podemos o assistir de acordo com as regras impostas pelo desafio. Pra isso, quando nos deparamos com um novo filme, primeiro checamos se os horários que ele ocupa não está sendo ocupado por nenhum outro filme que ja assistimos. Depois checamos se ja alcancamos o limite de sua categoria. Se essas duas regras não forem quebradas, assistimos o filme e atualizamos o vetor de filmes assistidos, os horários ocupados por esse filme e adicionamos 1 no vetor que toma conta dos limites de categoria.

A Heurística Aleatória

Diferente do que o nome sugere, a nossa heurística aleatória na verdade é apenas um pouco aleatória.

A heurística aleatória segue as mesmas regras da heurística gulosa, porém com uma diferenciação. 25% das vezes, ao invés de seguir a lista ordenada de filmes, o algoritimo que segue a heurística aleatória irá selecionar um filme qualquer que ainda não tenha sido assistido e que não quebre nenhuma das regras do desafio.

A aleatoriedade é interessante pois a heurística puramente gulosa pode se prender em um ótimo local. Se de vez em quando o algorítimo é induzido a selecionar um filme aleatório, ele pode sair do ótimo local.

Código fonte da heurística aleatória

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

// Define a struct to represent a movie
struct Movie {
    int start_time;
    int end_time;
    int category;
};

bool check_can_watch(const Movie& movie, const bitset<24>& hours, const vector<int>& num_watched, const vector<int>& category_limit) {
    if (num_watched[movie.category] >= category_limit[movie.category]) { return false; }
    for (int hour = movie.start_time; hour < movie.end_time; hour++) {
        if (hours[hour]) {
            return false;
        }
    }
    if (hours[movie.start_time]) { return false; }
    return true;
}

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();

    srand((unsigned) time(NULL));
    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    // Read the category limits into a vector
    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    // Read the movie information into a vector
    vector<Movie> unwatched_movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> unwatched_movies[i].start_time >> unwatched_movies[i].end_time >> unwatched_movies[i].category;
        if (unwatched_movies[i].end_time < unwatched_movies[i].start_time) {
            unwatched_movies[i].end_time = 24;
        }

        if (unwatched_movies[i].end_time == unwatched_movies[i].start_time) {
            unwatched_movies[i].end_time += 1;
        }
    }

    vector<Movie> watched_movies;
    vector<Movie> lost_movies;

    // Sort the movies by end time
    sort(unwatched_movies.begin(), unwatched_movies.end(), [](const Movie& a, const Movie& b) {
        if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
        return a.end_time < b.end_time;
    });

    // Define a bitset to represent the availability of each hour of the day
    bitset<24> hours;

    // Keep track of how many movies of each category have been watched
    vector<int> num_watched(num_categories + 1, 0);

    int time_watched = 0;

    // Iterate over the movies and check if each movie can be watched
    while (!unwatched_movies.empty()) {
        bool end = false;
        Movie movie;
        int index;
        int random_num = rand() % 4;
        if (random_num != 0) {
            index = 0;
            movie = unwatched_movies.front();
        } else {
            index = rand() % unwatched_movies.size();
            movie = unwatched_movies[index];

            while(!check_can_watch(movie, hours, num_watched, category_limit)) {
                lost_movies.push_back(movie);
                unwatched_movies.erase(unwatched_movies.begin() + index);

                if (unwatched_movies.empty()) { end = true; break; }

                index = rand() % unwatched_movies.size();
                movie = unwatched_movies[index];
            }
        }

        if (end) { break; }

        if (check_can_watch(movie, hours, num_watched, category_limit)) {
            hours[movie.start_time] = true;
            for (int hour = movie.start_time; hour < movie.end_time; hour++) {
                hours[hour] = true;
            }
            num_watched[movie.category]++;
            time_watched += movie.end_time - movie.start_time;
            watched_movies.push_back(movie);
            unwatched_movies.erase(unwatched_movies.begin()+index);
            cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
        } else {
            lost_movies.push_back(movie);
            unwatched_movies.erase(unwatched_movies.begin() + index);
        }
    }

    // Output the number of watched movies
    cout << "\nNúmero de filmes: " << watched_movies.size() << endl;
    cout << "Tempo de tela (em horas): " << time_watched << endl;

    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the stochastic greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação da heurística

  1. Tratamento do input

Sempre começamos tratando os dados do input. Recebemos como entrada do nosso programa um arquivo na seguinte estrutura: primeira linha contem dois números, o número total de filmes e o número total de categorias. A segunda linha possui os limites de cada categoria. As linhas seguintes definem os filmes. Cada uma delas possuem 3 números, horário de início, horário de término e categoria. Começamos montando uma estrutura de dados para representar cada filme. Depois, transformamos os limites de cada categoria em um vetor e os filmes em um vetor de filmes.

  1. Ordenação

O segundo passo é ordenar o vetor de filmes por horário de término.

  1. Uso do bitset

Usamos um bitset para organizar quais horas do dia estão livres para assisitirmos um filme. Sempre que um novo filme é assistido, preenchemos o bitset nos horários que o filme nos ocupou.

  1. Validação do filme seguinte

Essa etapa, na heurística aleatória, é diferente da heurística gulosa. Em 75% das vezes vamos seguir o mesmo procedimento da heurística gulosa, porém em 25% das vezes, iremos assistir um filme aleatório da lista que ainda não foi assistido e se encaixa nas regras do desafio.

Profiling com Valgrind

Profiling da heurística gulosa

-- line 7 ----------------------------------------
     .
     .           // Define a struct to represent a movie
     .           struct Movie {
     .               int start_time;
     .               int end_time;
     .               int category;
     .           };
     .
    11 ( 0.00%)  int main() {
     .               int num_movies, num_categories;
     6 ( 0.00%)      cin >> num_movies >> num_categories;
 8,589 ( 0.14%)  => ???:0x0000000000109150 (2x)
     .
     .               // Read the category limits into a vector
     3 ( 0.00%)      vector<int> category_limit(num_categories + 1);
    45 ( 0.00%)      for (int i = 1; i <= num_categories; i++) {
    32 ( 0.00%)          cin >> category_limit[i];
10,442 ( 0.18%)  => ???:0x0000000000109150 (10x)
     .               }
     .
     .               // Read the movie information into a vector
     1 ( 0.00%)      vector<Movie> movies(num_movies);
 4,006 ( 0.07%)      for (int i = 0; i < num_movies; i++) {
 9,002 ( 0.15%)          cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
3,292,381 (55.46%)  => ???:0x0000000000109150 (3,000x)
 3,000 ( 0.05%)          if (movies[i].end_time < movies[i].start_time) {
   135 ( 0.00%)              movies[i].end_time = 24;
     .                   }
     .               }
     .
     .               // Sort the movies by end time
     .               sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
24,984 ( 0.42%)          if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
19,774 ( 0.33%)          return a.end_time < b.end_time;
     .               });
     .
     .               // // Sort the movies by start time
     .               // sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
     .               //     return a.start_time < b.start_time;
     .               // });
     .
     .               // Define a bitset to represent the availability of each hour of the day
     1 ( 0.00%)      bitset<24> hours;
     .
     .               // Keep track of how many movies of each category have been watched
     3 ( 0.00%)      vector<int> num_watched(num_categories + 1, 0);
     .
     .               // Keep track of the indices of the watched movies
     .               vector<int> watched;
     .
     .               // Iterate over the movies and check if each movie can be watched
 4,007 ( 0.07%)      for (int i = 0; i < num_movies; i++) {
 1,000 ( 0.02%)          const Movie& movie = movies[i];
     .
     .                   // Check if any hour of the movie overlaps with an already watched movie
     .                   bool can_watch = true;
 7,075 ( 0.12%)          for (int hour = movie.start_time; hour < movie.end_time; hour++) {
 2,963 ( 0.05%)              if (hours[hour]) {
     .                           can_watch = false;
     .                           break;
     .                       }
     .                   }
    25 ( 0.00%)          if (hours[movie.start_time]) { can_watch = false; }
     .
     .                   // If the movie can be watched and its category limit has not been reached,
     .                   // mark the hours as watched, add the movie to the list of watched movies,
     .                   // and print the start time, end time, and category of the movie
   108 ( 0.00%)          if (can_watch && num_watched[movie.category] < category_limit[movie.category]) {
    40 ( 0.00%)              num_watched[movie.category]++;
     .                       watched.push_back(i);
    20 ( 0.00%)              hours[movie.start_time] = true;
   137 ( 0.00%)              for (int hour = movie.start_time; hour < movie.end_time; hour++) {
     .                           hours[hour] = true;
     .                       }
   180 ( 0.00%)              cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
31,724 ( 0.53%)  => ???:0x00000000001091e0 (60x)
     .                   }
     .               }
     .
     .               // Output the number of watched movies
     .               // cout << watched.size() << endl;
     .
     .               return 0;
    15 ( 0.00%)  }

Profiling da heurística aleatória

-- line 8 ----------------------------------------
     .           // Define a struct to represent a movie
     .           struct Movie {
     .               int start_time;
     .               int end_time;
     .               int category;
     .           };
     .
     .           bool check_can_watch(const Movie& movie, const bitset<24>& hours, const vector<int>& num_watched, const vector<int>& category_limit) {
 4,121 ( 0.05%)      if (num_watched[movie.category] >= category_limit[movie.category]) { return false; }
 7,200 ( 0.09%)      for (int hour = movie.start_time; hour < movie.end_time; hour++) {
 1,756 ( 0.02%)          if (hours[hour]) {
     .                       return false;
     .                   }
     .               }
    16 ( 0.00%)      if (hours[movie.start_time]) { return false; }
     .               return true;
     .           }
     .
    11 ( 0.00%)  int main() {
     4 ( 0.00%)      srand((unsigned) time(NULL));
 6,817 ( 0.08%)  => ???:0x0000000000109220 (1x)
     8 ( 0.00%)  => ???:0x0000000000109200 (1x)
     .               int num_movies, num_categories;
     6 ( 0.00%)      cin >> num_movies >> num_categories;
 8,589 ( 0.10%)  => ???:0x00000000001091c0 (2x)
     .
     .               // Read the category limits into a vector
     3 ( 0.00%)      vector<int> category_limit(num_categories + 1);
    45 ( 0.00%)      for (int i = 1; i <= num_categories; i++) {
    32 ( 0.00%)          cin >> category_limit[i];
10,442 ( 0.13%)  => ???:0x00000000001091c0 (10x)
     .               }
     .
     .               // Read the movie information into a vector
     6 ( 0.00%)      vector<Movie> unwatched_movies(num_movies);
 1,750 ( 0.02%)  => /usr/include/c++/9/bits/stl_vector.h:std::vector<Movie, std::allocator<Movie> >::vector(unsigned long, std::allocator<Movie> const&) (1x)
 4,006 ( 0.05%)      for (int i = 0; i < num_movies; i++) {
 9,002 ( 0.11%)          cin >> unwatched_movies[i].start_time >> unwatched_movies[i].end_time >> unwatched_movies[i].category;
3,292,381 (40.23%)  => ???:0x00000000001091c0 (3,000x)
 4,000 ( 0.05%)          if (unwatched_movies[i].end_time < unwatched_movies[i].start_time) {
   135 ( 0.00%)              unwatched_movies[i].end_time = 24;
     .                   }
     .               }
     .
     7 ( 0.00%)      vector<Movie> watched_movies(num_movies);
 1,750 ( 0.02%)  => /usr/include/c++/9/bits/stl_vector.h:std::vector<Movie, std::allocator<Movie> >::vector(unsigned long, std::allocator<Movie> const&) (1x)
     6 ( 0.00%)      vector<Movie> lost_movies(num_movies);
 1,750 ( 0.02%)  => /usr/include/c++/9/bits/stl_vector.h:std::vector<Movie, std::allocator<Movie> >::vector(unsigned long, std::allocator<Movie> const&) (1x)
     .
     .               // Sort the movies by end time
     .               sort(unwatched_movies.begin(), unwatched_movies.end(), [](const Movie& a, const Movie& b) {
24,984 ( 0.31%)          if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
19,774 ( 0.24%)          return a.end_time < b.end_time;
     .               });
     .
     .               // Define a bitset to represent the availability of each hour of the day
     2 ( 0.00%)      bitset<24> hours;
     .
     .               // Keep track of how many movies of each category have been watched
     3 ( 0.00%)      vector<int> num_watched(num_categories + 1, 0);
     .
     .               // Keep track of the indices of the watched movies
     .               vector<int> watched;
     .
     .               // Iterate over the movies and check if each movie can be watched
    79 ( 0.00%)      while (!unwatched_movies.empty()) {
     .                   bool end = false;
     .                   Movie movie;
     .                   int index;
    39 ( 0.00%)          int random_num = rand() % 4;
 2,406 ( 0.03%)  => ???:0x0000000000109190 (39x)
    78 ( 0.00%)          if (random_num != 0) {
    26 ( 0.00%)              index = 0;
   130 ( 0.00%)              movie = unwatched_movies.front();
     .                   } else {
    91 ( 0.00%)              index = rand() % unwatched_movies.size();
   806 ( 0.01%)  => ???:0x0000000000109190 (13x)
   104 ( 0.00%)              movie = unwatched_movies[index];
     .
   961 ( 0.01%)              while(!check_can_watch(movie, hours, num_watched, category_limit)) {
     .                           lost_movies.push_back(movie);
     .                           unwatched_movies.erase(unwatched_movies.begin() + index);
     .
 1,925 ( 0.02%)                  if (unwatched_movies.empty()) { end = true; break; }
     .
 5,766 ( 0.07%)                  index = rand() % unwatched_movies.size();
59,466 ( 0.73%)  => ???:0x0000000000109190 (961x)
 6,727 ( 0.08%)                  movie = unwatched_movies[index];
     .                       }
     .                   }
     .
     .                   if (end) { break; }
     .
     .                   if (check_can_watch(movie, hours, num_watched, category_limit)) {
     .                       hours[movie.start_time] = true;
    92 ( 0.00%)              for (int hour = movie.start_time; hour < movie.end_time; hour++) {
     .                           hours[hour] = true;
     .                       }
    28 ( 0.00%)              num_watched[movie.category]++;
     .                       watched_movies.push_back(movie);
     .                       unwatched_movies.erase(unwatched_movies.begin()+index);
   168 ( 0.00%)              cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
24,477 ( 0.30%)  => ???:0x00000000001092a0 (42x)
     .                   } else {
     .                       lost_movies.push_back(movie);
     .                       unwatched_movies.erase(unwatched_movies.begin() + index);
     .                   }
     .               }
     .
     .               // Output the number of watched movies
     .               // cout << watched.size() << endl;
     .
     .               return 0;
    15 ( 0.00%)  }

Conclusões sobre o profiling

Podemos notar que as instruções de ler dados de um arquivo e de escrever dados para o stdout são as instruções que mais consomem. Além disso, as instruções que involvem calculode variáveis com aleatoriedade também impactam muito.

Comparação de Resultados

Visualização comparativa entre a performance da heurística gulosa e aleatória

Para criar essas visualizações foram levadas em consideração as seguintes variáveis:

Conclusão dos resultados das heurísticas

Analisando os resultados, podemos concluir que a performance da heurística gulosa é melhor do que a performance da heurística aleatória para todas as métricas comparadas.

Para todos os inputs, a heurística gulosa assisitiu um número maior ou igual ao número de filmes assistidos pela heurística com aleatoriedade.

Para todos os inputs, a heurística gulosa passou mais tempo assistindo filmes ou a mesma quantidade de tempo que a heurística com aleatoriedade

Para todos os inputs, o tempo de execução da heurística gulosa foi menor do que o tempo de execução da heurística aleatória.

A Solução Exaustiva

A técnica de força bruta é uma abordagem de resolução de problemas que tenta todas as possibilidades até que uma solução ótima seja encontrada.

Neste problema de agendamento de filmes, vamos gerar todas as possíveis combinações de filmes e verificar se cada combinação é válida. Aqui, uma combinação é considerada válida se nenhum filme na combinação tem tempos de exibição que se sobrepõem e se o número de filmes em cada categoria não excede o limite especificado para essa categoria.

Existem 2^n possíveis combinações de n filmes, onde "n" é o número total de filmes.

Vamos implementar a solução exaustiva de 4 formas diferentes:

  1. Uma solução com recursividade. Vamos usar estratégias de recursão (uma função que chama ela mesma) para executar a busca exaustiva.

  2. Uma solução iterativa sem recursividade. Vamos implementar busca exaustiva sem o uso de recursão e usando apenas "loops".

  3. Uma solução de computação paralela utilizando OpenMP. utilizando a biblioteca OpenMP, vamos dividir a execução da busca em alguns threads no nosso computador.

  4. Uma solução que usa paralelismo na GPU. Utilizando Thrust, vamos implementar uma solução para esse problema que pode ser paralelizada em uma GPU.

Código fonte da solução recursiva

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;

struct Movie {
    int start_time;
    int end_time;
    int category;
};

// function to check if two movies overlap
bool isOverlap(const Movie &a, const Movie &b) {
    return a.start_time < b.end_time && b.start_time < a.end_time;
}

// function to check if a list of movies is valid
bool isValid(const vector<Movie> &movies, const vector<int> &category_limit) {
    vector<int> category_count(category_limit.size(), 0);
    for (size_t i = 0; i < movies.size(); i++) {
        category_count[movies[i].category]++;
        if (category_count[movies[i].category] > category_limit[movies[i].category])
            return false;
        for (size_t j = i + 1; j < movies.size(); j++)
            if (isOverlap(movies[i], movies[j]))
                return false;
    }
    return true;
}

// recursive function to generate all possible combinations
void exhaustiveSearch(vector<Movie> &movies, vector<int> &category_limit,
                     vector<Movie> &current, vector<Movie> &best, int i) {
    if (i == movies.size()) {
        if (current.size() > best.size())
            best = current;
        return;
    }
    exhaustiveSearch(movies, category_limit, current, best, i + 1);
    current.push_back(movies[i]);
    if (isValid(current, category_limit))
        exhaustiveSearch(movies, category_limit, current, best, i + 1);
    current.pop_back();
}

int main() {
    auto startTime = chrono::steady_clock::now();
    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    vector<Movie> movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
        if (movies[i].end_time < movies[i].start_time) {
            movies[i].end_time = 24;
        }

        if (movies[i].end_time == movies[i].start_time) {
            movies[i].end_time += 1;
        }
    }

    vector<Movie> current;
    vector<Movie> best;
    exhaustiveSearch(movies, category_limit, current, best, 0);

    for (const Movie &movie : best) {
        cout << movie.start_time << " " << movie.end_time << " " << movie.category << "\n";
    }

    cout << "\nNúmero de filmes: " << best.size() << "\n";
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the brute-force algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação da solução com recursividade

Existem duas funções auxiliares no código. A função 'isOverlap()' verifica se dois filmes se sobrepõem no tempo. A outra função auxiliar, 'isValid()', verifica se uma lista de filmes é válida. Uma lista é considerada válida se nenhum dos filmes se sobrepõe e se o número de filmes em cada categoria não excede o limite especificado para essa categoria.

A função 'exhaustiveSearch()' é uma função recursiva que gera todas as possíveis combinações de filmes. Para cada combinação, ela verifica se a combinação é válida. Se a combinação for válida e tiver mais filmes do que a melhor combinação encontrada até então, essa combinação se torna a nova melhor combinação.

Na função principal, o código faz o seguinte: Primeiro, lê o número de filmes e categorias e os limites para cada categoria da entrada padrão. Em seguida, lê os detalhes de cada filme. Depois, chama a função 'exhaustiveSearch()' para encontrar a melhor combinação de filmes. Finalmente, imprime a melhor combinação de filmes e o número de filmes na melhor combinação.

Código fonte da solução iterativa (sem recursão)

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

using namespace std;

struct Movie {
    int start_time;
    int end_time;
    int category;
};

bool isOverlap(const Movie &a, const Movie &b) {
    return a.start_time < b.end_time && b.start_time < a.end_time;
}

bool isValid(const vector<Movie> &schedule, const vector<int> &category_limit) {
    vector<int> category_count(category_limit.size(), 0);
    for (size_t i = 0; i < schedule.size(); i++) {
        category_count[schedule[i].category]++;
        if (category_count[schedule[i].category] > category_limit[schedule[i].category])
            return false;
        for (size_t j = i + 1; j < schedule.size(); j++)
            if (isOverlap(schedule[i], schedule[j]))
                return false;
    }
    return true;
}

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();
    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    vector<Movie> movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
        if (movies[i].end_time < movies[i].start_time) {
            movies[i].end_time = 24;
        }

        if (movies[i].end_time == movies[i].start_time) {
            movies[i].end_time += 1;
        }
    }

    vector<Movie> best_schedule;
    for (int bit = 0; bit < (1 << num_movies); bit++) {
        vector<Movie> current_schedule;
        for (int i = 0; i < num_movies; i++) {
            if (bit & (1 << i)) {
                current_schedule.push_back(movies[i]);
            }
        }

        if (isValid(current_schedule, category_limit) && current_schedule.size() > best_schedule.size()) {
            best_schedule = current_schedule;
        }
    }

    for (const Movie &movie : best_schedule) {
        cout << movie.start_time << " " << movie.end_time << " " << movie.category << "\n";
    }

    cout << "\nNúmero de filmes: " << best_schedule.size() << "\n";
    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação da solução iterativa

Essa solução é muito similar ao algorítimo recursivo, porém ao invés de usar recursividade para fazer a busca exaustiva, realiza a busca com loops.

O programa principal começa registrando o horário de início para futura referência. Depois, lê o número de filmes e categorias. Em seguida, lê o limite para cada categoria e as informações de cada filme, garantindo que os horários de término são posteriores aos horários de início e que nenhum filme tem duração zero.

O programa então cria todas as combinações possíveis de agendamentos de filmes, utilizando uma técnica de força bruta. Para cada combinação, o programa verifica se o agendamento é válido e se é melhor (ou seja, inclui mais filmes) do que o melhor agendamento encontrado até agora. Se ambas as condições forem verdadeiras, o agendamento atual se torna o novo melhor agendamento.

Finalmente, o programa imprime o melhor agendamento encontrado, bem como o número total de filmes nesse agendamento. Além disso, ele calcula e imprime o tempo total de execução do algoritmo.

Código fonte da solução paralelizada utilizando OpenMP

#include <iostream>
#include <vector>
#include <algorithm>
#include <omp.h>
#include <chrono>

using namespace std;

struct Movie {
    int start_time;
    int end_time;
    int category;
};

bool isOverlap(const Movie &a, const Movie &b) {
    return a.start_time < b.end_time && b.start_time < a.end_time;
}

bool isValid(const vector<Movie> &schedule, const vector<int> &category_limit) {
    vector<int> category_count(category_limit.size(), 0);
    for (size_t i = 0; i < schedule.size(); i++) {
        category_count[schedule[i].category]++;
        if (category_count[schedule[i].category] > category_limit[schedule[i].category])
            return false;
        for (size_t j = i + 1; j < schedule.size(); j++)
            if (isOverlap(schedule[i], schedule[j]))
                return false;
    }
    return true;
}

int main() {
    auto startTime = chrono::steady_clock::now();
    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    vector<Movie> movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
        if (movies[i].end_time < movies[i].start_time) {
            movies[i].end_time = 24;
        }

        if (movies[i].end_time == movies[i].start_time) {
            movies[i].end_time += 1;
        }
    }

    vector<Movie> best_schedule;

    #pragma omp parallel for
    for (int bit = 0; bit < (1 << num_movies); bit++) {
        vector<Movie> current_schedule;
        for (int i = 0; i < num_movies; i++) {
            if (bit & (1 << i)) {
                current_schedule.push_back(movies[i]);
            }
        }

        if (isValid(current_schedule, category_limit)) {
            #pragma omp critical
            {
                if (current_schedule.size() > best_schedule.size()) {
                    best_schedule = current_schedule;
                }
            }
        }
    }

    for (const Movie &movie : best_schedule) {
        cout << movie.start_time << " " << movie.end_time << " " << movie.category << "\n";
    }

    cout << "\nNúmero de filmes: " << best_schedule.size() << "\n";
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the brute-force algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação da solução utilizando OpenMP

A estrutura Movie e as funções isOverlap e isValid são idênticas ao programa anterior. A diferença fundamental entre os dois programas está na função main.

O início da função main também é idêntico ao programa anterior, onde o código captura o horário de início, lê o número de filmes e categorias, lê os limites de cada categoria e lê as informações de cada filme. A diferença começa quando o código começa a criar todas as possíveis combinações de agendamentos de filmes.

O comando / diretiva #pragma omp parallel for antes do loop for é uma diretiva do OpenMP que instrui o compilador a executar o loop em paralelo. Isso significa que o trabalho de iterar sobre todas as possíveis combinações de agendamentos de filmes é dividido entre vários threads, cada um dos quais executa uma parte do trabalho.

O código dentro do loop é quase o mesmo do programa anterior, mas com uma diferença fundamental. Quando um agendamento válido é encontrado, o código entra em uma seção crítica, protegida pela diretiva #pragma omp critical. Esta seção do código só pode ser executada por um thread de cada vez. Isso é necessário porque o acesso à variável best_schedule, que é compartilhada por todos os threads, precisa ser protegido para evitar condições de corrida, onde dois ou mais threads tentam atualizar a variável ao mesmo tempo.

Código fonte da solução paralelizada em GPU com Thrust

// Include the necessary libraries
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
#include <thrust/transform.h>
#include <thrust/fill.h>
#include <thrust/copy.h>
#include <iostream>
#include <cassert>
#include <random>
#include <chrono>
#include <math.h>

using namespace std;

// Definindo o struct
struct Movie {
  int start;
  int end;
  int category;
};

// Definindo o functor
struct ScheduleFunctor {
  int movieCount;  // Number of movies
  int categoryCount;  // Number of categories
  int *categoryLimits;  // Limits for each category
  Movie *movies;  // List of movies

  ScheduleFunctor(int movieCount, Movie *movies, int categoryCount, int *categoryLimits)
      : movieCount(movieCount), movies(movies), categoryCount(categoryCount), categoryLimits(categoryLimits) {}

  // Função principal do functor que avalia quantos filmes poderão ser assistido de forma válida dado uma combinação.
  __device__ __host__
  int operator()(int combination) {
    bool timeSlots[24] = {false}; 

    // criação do vetor do limite de categorias
    int localCategoryLimits[20];
    for (int i = 0; i <= categoryCount; i++) {
      localCategoryLimits[i] = categoryLimits[i];
    }

    int scheduledMovies = 0;  // Counter 
    for (int i = 0; i < movieCount; i++) {
      if (combination & (1 << i)) {  // Check if the i-th movie is included in the combination
        Movie& currentMovie = movies[i];

        // Validação de overlap
        for (int j = currentMovie.start; j < currentMovie.end; j++) {
          if (timeSlots[j]) return -1; 
          timeSlots[j] = true;  
        }
        // Validação de limite de categoria
        if (localCategoryLimits[currentMovie.category] == 0) return -1;
        localCategoryLimits[currentMovie.category]--;  // Decremento do limite para quela categoria (se o filme for assistido)
        scheduledMovies++;
      }
    }
    return scheduledMovies;
  }
};

// Main function
int main(int argc, char *argv[]) {
  // Lê num filmes e num categorias
  int num_movies, num_categories;
  cin >> num_movies >> num_categories;

  // Lê limite por categroia
  vector<int> category_limit(num_categories + 1);
  for (int i = 1; i <= num_categories; i++) {
    cin >> category_limit[i];
  }

  // Lê filmes
  vector<Movie> movies(num_movies);
  for (int i = 0; i < num_movies; i++) {
    cin >> movies[i].start >> movies[i].end >> movies[i].category;
    if (movies[i].end < movies[i].start) {
      movies[i].end = 24;
    }

    if (movies[i].end == movies[i].start) {
      movies[i].end += 1;
    }
  }

  auto startTime = chrono::steady_clock::now();

  // Aloca GPU
  int *category_limit_gpu;
  Movie *movies_gpu;
  cudaMalloc(&category_limit_gpu, category_limit.size() * sizeof(int));
  cudaMalloc(&movies_gpu, movies.size() * sizeof(Movie));
  cudaMemcpy(category_limit_gpu, category_limit.data(), category_limit.size() * sizeof(int), cudaMemcpyHostToDevice);
  cudaMemcpy(movies_gpu, movies.data(), movies.size() * sizeof(Movie), cudaMemcpyHostToDevice);

  thrust::device_vector<int> movie_counts(pow(2, movies.size()));
  thrust::counting_iterator<int> combinations(0);

  ScheduleFunctor functor(
    movies.size(), 
    movies_gpu, 
    num_categories, 
    category_limit_gpu
  );

  // Roda o algoritimo usando o functor
  thrust::transform(combinations, combinations + pow(2, movies.size()), movie_counts.begin(), functor);

  // Encontrar o número máximo de filmes que podem ser assistido. Esse numero vai ser o maior número no vetor movie_counts.
  //   int max_movies = thrust::reduce(movie_counts.begin(), movie_counts.end(), thrust::maximum<int>())
  int max_movies = *thrust::max_element(movie_counts.begin(), movie_counts.end());

  // Print the result
  cout << "\nNúmero de filmes: " << max_movies << "\n";

  auto endTime = chrono::steady_clock::now();
  double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

  // Print the elapsed time
  cout << fixed;
  cout << "Time elapsed during the brute-force algorithm (in microseconds): " << duration << endl;
  cout << scientific;

  cudaFree(category_limit_gpu);
  cudaFree(movies_gpu);

  return 0;
}

Explicação da solução utilizando Thrust

Nessa solução, definimos um "functor" chamado "ScheduleFunctor". Este é um tipo especial de estrutura que pode ser usada como uma função. O functor é inicializado com informações sobre o número de filmes, a lista de filmes, o número de categorias e os limites de cada categoria.

O operador de função do functor avalia um dado agendamento de filmes, representado como um inteiro no qual cada bit representa se um determinado filme está incluído ou não no agendamento. verificamos se os filmes no agendamento não se sobrepõem no tempo e não excedem os limites de categoria. Retornamos, então, o número total de filmes no agendamento, ou -1 se o agendamento não for válido.

Na função main, o programa lê o número de filmes e categorias e as informações sobre cada filme da entrada padrão (como nas outras implementações). Depois, alocamos memória na GPU para a lista de filmes e os limites de categoria e copia essas informações para a GPU.

A biblioteca Thrust é usada para criar um vetor device na GPU para armazenar o número de filmes que podem ser agendados para cada combinação possível. Usamos a função transform do Thrust para aplicar o functor a cada combinação possível e armazenar o resultado no vetor device.

Em seguida, usamos a função max_element do Thrust para encontrar a combinação com o maior número de filmes que podem ser agendados e imprimimos esse número.

Para essa implementação, tem um limite para quantas categorias podem existir.

Comparação dos resultados

Como esperado, todos os algorítimos de força bruta assistem a mesma quantidade de filmes.

Isso é esperado pois como eles testam todas as opções possíveis e escolhem a melhor. Chegam no mesmo resultado, independente do caminho.

Conclusão

Para concluir, nós conseguimos ver que a heurística Gulosa e Aleatória tiveram um desempenho com relação a tempo de execução muito superior a todas as implementações de Brute force, porém nem sempre chegaram na solução mais otimizada.

Em compensação, as soluções brute-force conseguem otimizar o resultado, nesse caso, assisitr o maior número possível de filmes dadas as restrições, mas demoram muito mais tempo para executar.

Vemos que a GPU realmente consegue acelerar muito a execução do algorítimo de brute force. Quando o input é muito pequeno, o brute force sem aceleração por GPU tem um desempenho maior já que o uso da GPU tem um custo para iniciar e armazenar os vetores na memória da GPU.

Podemos dizer que se o conjunto de dados não for muito grande (aliás, for pequeno), usar uma tecnica de brute force é uma boa opção. Já se o conjunto de dados e restrições for grande, teremos que recorrer para outro método.